Primes in Arithmetic Progressions

Introduction

Many primes have simple algebraic shapes:
- $2k+1$ (all odd numbers)
- $6k\pm 1$ (all primes greater than $3$)
- $4k+1$ and $4k+3$ (odd numbers split into two families)
A natural question: Are there infinitely many primes of the form $4k+1$?
This article explores:
- What arithmetic progressions are
- Why primes in progressions matter
- What mathematicians know (and don’t know)
- A gentle peek at Dirichlet’s Theorem
- Examples, patterns, and exercises

Arithmetic Progressions and the Form $4k+1$

An arithmetic progression is a sequence of numbers with a constant step:
- $a, a+d, a+2d, a+3d, \dots$
The form $4k+1$ is the progression:
- $1, 5, 9, 13, 17, 21, 25, \dots$
Odd numbers split neatly into:
- $4k+1$: $1,5,9,13,17,\dots$
- $4k+3$: $3,7,11,15,19,\dots$
Many primes appear in both families:
- $4k+1$ primes: $5,13,17,29,37,41,\dots$
- $4k+3$ primes: $3,7,11,19,23,31,\dots$

Why This Question Matters

Understanding primes in progressions helps us see structure inside randomness.
The question “Are there infinitely many primes of the form $4k+1$?” is a special case of a much bigger idea:
- How are primes distributed among different arithmetic patterns?
This leads to:
- Deeper number theory
- Connections to modular arithmetic
- Tools used in cryptography
- Insights into symmetry and residues

A Quick Review of Modular Arithmetic

Modular arithmetic studies numbers “wrapped around” a modulus.
Saying $n \equiv 1 \pmod{4}$ means:
- $n$ leaves remainder $1$ when divided by $4$.
The four possible remainders mod $4$ are:
- $0,1,2,3$
Odd numbers are exactly those with remainder $1$ or $3$ mod $4$.
This language helps us talk precisely about the shape $4k+1$.

First Observations and Small Examples

Let’s list primes up to $100$ and classify them:
- Primes of the form $4k+1$: $$5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97$$
- Primes of the form $4k+3$: $$3, 7, 11, 19, 23, 31, 43, 47, 59, 67, 71, 79, 83$$
Observations:
- Both families appear frequently.
- Neither seems to “run out”.
- But small data can be misleading — we need theory.

Patterns in Primes: What We Can and Cannot See

What we can see:
- Roughly half of the odd primes seem to be $4k+1$.
- The other half seem to be $4k+3$.
- No obvious pattern predicts the next prime.
What we cannot conclude from data alone:
- Infinitude (we can’t check infinitely many cases)
- Exact proportions
- Deep structural reasons
This motivates the need for theoretical tools.

The Role of Quadratic Residues

A quadratic residue mod $n$ is a number that is a square modulo $n$.
For example, modulo $4$:
- Squares are $0^2=0$, $1^2=1$, $2^2=0$, $3^2=1$
- So the only quadratic residues mod $4$ are $0$ and $1$.
A key fact (stated without proof):
- A prime $p$ is of the form $4k+1$ if and only if $-1$ is a quadratic residue mod $p$.
Meaning:
- There exists an integer $x$ such that $$x^2 \equiv -1 \pmod{p}$$
exactly when $p \equiv 1 \pmod{4}$.
This surprising link connects prime shapes to solvable equations.

A Glimpse of Dirichlet’s Theorem

Dirichlet’s Theorem on Arithmetic Progressions (informal version):
- If $a$ and $d$ are coprime, then the progression $$a,\, a+d,\, a+2d,\, a+3d,\, \dots$$
contains infinitely many primes.
For our case:
- $a=1$, $d=4$, and $\gcd(1,4)=1$
- Therefore, there are infinitely many primes of the form $4k+1$.
This theorem is deep:
- Uses ideas from analysis
- Involves $L$‑functions
- Cannot be proved with elementary tools alone
But the conclusion is simple and beautiful.

How Mathematicians Prove Infinitude in Progressions

Without going into heavy machinery, here are the broad ideas:

Step 1: Study how primes behave in modular arithmetic.
Step 2: Build analytic tools that measure how often primes appear.
Step 3: Show that primes cannot “avoid” any progression with $\gcd(a,d)=1$.
Step 4: Conclude that each such progression must contain infinitely many primes.

For the special case of $4k+1$:

The structure of quadratic residues plays a role.
Symmetry in modular arithmetic helps distribute primes evenly.
Analytic tools guarantee infinitude.

Consequences and Applications

Symmetry of primes:
Primes are evenly distributed between $4k+1$ and $4k+3$ in the long run.
Gaussian integers:
Primes of the form $4k+1$ factor in the complex integer lattice $\mathbb{Z}[i]$.
Cryptography:
Some cryptographic protocols rely on primes with specific modular properties.
Further generalizations:
- Primes of the form $ak+b$
- Primes in longer patterns
- Twin primes and other conjectures

Summary

Arithmetic progressions give structure to the integers.
The form $4k+1$ is one of the simplest nontrivial progressions.
Data suggests many primes of this form — theory confirms infinitely many.
Dirichlet’s Theorem guarantees infinitude whenever $a$ and $d$ are coprime.
The case $4k+1$ connects beautifully to quadratic residues and Gaussian integers.

Exercises

Classify primes: List all primes below $200$ and classify them as $4k+1$ or $4k+3$.
Solution
- Primes below $200$ $$2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199$$
- Of the form $4k+1$ (remainder $1$ mod $4$): $$5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,193$$
- Of the form $4k+3$ (remainder $3$ mod $4$): $$3,7,11,19,23,31,43,47,59,67,71,79,83,103,107,127,131,139,151,163,167,179,191,197,199$$
- Note: $2$ is even, so it does not fit $4k+1$ or $4k+3$.
Modular practice: Compute the remainder of the following numbers mod $4$:
$57, 98, 123, 201, 314$.
Solution
Compute $n \bmod 4$:
- $57$:
  $56$ is divisible by $4$, so $57 \equiv 1 \pmod{4}$.
- $98$:
  $96$ is divisible by $4$, so $98 \equiv 2 \pmod{4}$.
- $123$:
  $120$ is divisible by $4$, so $123 \equiv 3 \pmod{4}$.
- $201$:
  $200$ is divisible by $4$, so $201 \equiv 1 \pmod{4}$.
- $314$:
  $312$ is divisible by $4$, so $314 \equiv 2 \pmod{4}$.
Quadratic residues mod $4$: Verify that the only quadratic residues mod $4$ are $0$ and $1$.
Solution
Compute $x^2 \bmod 4$ for $x=0,1,2,3$:
- $x=0$: $0^2 = 0 \equiv 0 \pmod{4}$
- $x=1$: $1^2 = 1 \equiv 1 \pmod{4}$
- $x=2$: $2^2 = 4 \equiv 0 \pmod{4}$
- $x=3$: $3^2 = 9 \equiv 1 \pmod{4}$
So the only possible square remainders mod $4$ are $0$ and $1$.
Therefore, the quadratic residues mod $4$ are exactly $0$ and $1$.
Exploring $x^2 \equiv -1 \pmod{p}$: For $p=5, 13, 17$, find an $x$ such that $x^2 \equiv -1 \pmod{p}$.
Solution
We want $x^2 \equiv -1 \pmod{p}$, i.e. $x^2 \equiv p-1 \pmod{p}$.
- For $p=5$:
  We need $x^2 \equiv 4 \pmod{5}$.
  - $2^2 = 4 \equiv 4 \pmod{5}$
  - $3^2 = 9 \equiv 4 \pmod{5}$
  So $x \equiv 2,3 \pmod{5}$ are solutions.
- For $p=13$:
  We need $x^2 \equiv 12 \pmod{13}$.
  Try small $x$:
  - $5^2 = 25 \equiv 12 \pmod{13}$
  - $8^2 = 64 \equiv 12 \pmod{13}$
  So $x \equiv 5,8 \pmod{13}$ are solutions.
- For $p=17$:
  We need $x^2 \equiv 16 \pmod{17}$.
  - $4^2 = 16 \equiv 16 \pmod{17}$
  - $13^2 = 169 \equiv 16 \pmod{17}$
  So $x \equiv 4,13 \pmod{17}$ are solutions.
Prime hunting: Find the next five primes of the form $4k+1$ after $100$.
Solution
Check primes greater than $100$ and test $p \bmod 4$:
- $101 \equiv 1 \pmod{4}$
- $103 \equiv 3 \pmod{4}$
- $107 \equiv 3 \pmod{4}$
- $109 \equiv 1 \pmod{4}$
- $113 \equiv 1 \pmod{4}$
- $127 \equiv 3 \pmod{4}$
- $131 \equiv 3 \pmod{4}$
- $137 \equiv 1 \pmod{4}$
- $139 \equiv 3 \pmod{4}$
- $149 \equiv 1 \pmod{4}$
- First five primes of the form $4k+1$ after $100$:
  $101, 109, 113, 137, 149$.
Arithmetic progressions: Write the first ten terms of the progression $7 + 6k$.
Which of them are prime?
Solution
The progression is $a_k = 7 + 6k$ for $k=0,1,2,\dots$
- First ten terms:
  - $k=0$: $7$
  - $k=1$: $13$
  - $k=2$: $19$
  - $k=3$: $25$
  - $k=4$: $31$
  - $k=5$: $37$
  - $k=6$: $43$
  - $k=7$: $49$
  - $k=8$: $55$
  - $k=9$: $61$
- Check primality:
  - $7$ — prime
  - $13$ — prime
  - $19$ — prime
  - $25 = 5^2$ — not prime
  - $31$ — prime
  - $37$ — prime
  - $43$ — prime
  - $49 = 7^2$ — not prime
  - $55 = 5 \cdot 11$ — not prime
  - $61$ — prime
- Primes among them:
  $7, 13, 19, 31, 37, 43, 61$.
Coprimality check: For each pair $(a,d)$ below, determine whether $\gcd(a,d)=1$:
$(2,4)$, $(3,8)$, $(5,6)$, $(7,9)$.
Solution
Compute $\gcd(a,d)$ for each pair:
- $(2,4)$:
  $\gcd(2,4) = 2$ → not coprime.
- $(3,8)$:
  $\gcd(3,8) = 1$ → coprime.
- $(5,6)$:
  $\gcd(5,6) = 1$ → coprime.
- $(7,9)$:
  $\gcd(7,9) = 1$ → coprime.
So only $(2,4)$ is not coprime; the others are.
Exploration question: Why do you think the condition $\gcd(a,d)=1$ is necessary in Dirichlet’s theorem?
Give an intuitive explanation.
Solution
- Key idea:
  If $a$ and $d$ share a common factor $g>1$, then every term in the progression $$a,\, a+d,\, a+2d,\, a+3d,\dots$$ is divisible by $g$.
- Consequences:
  - All terms are multiples of $g$.
  - The only possible prime in the progression would be $g$ itself (if it appears).
  - After that, every term is composite (since it has $g$ as a factor).
- Conclusion:
  To have infinitely many primes in the progression, we must avoid this “built‑in” factor.
  That is exactly what $\gcd(a,d)=1$ guarantees.
Gaussian integers (optional challenge): Show that $5 = (2+i)(2-i)$ in $\mathbb{Z}[i]$.
Try the same for $13$.
Solution
We work in $\mathbb{Z}[i] = \{a+bi : a,b \in \mathbb{Z}\}$.
- Show $5 = (2+i)(2-i)$:
  - Compute: $$(2+i)(2-i) = 2\cdot 2 - 2i + 2i - i^2 = 4 - (-1) = 5.$$
  - So $5$ factors as claimed.
- Try the same for $13$:
  - Look for $a,b$ such that $$(a+bi)(a-bi) = a^2 + b^2 = 13.$$
  - Pairs $(a,b)$ with $a^2 + b^2 = 13$:
    - $2^2 + 3^2 = 4 + 9 = 13$.
  - So: $$(2+3i)(2-3i) = 4 + 9 = 13.$$
- Conclusion:
  - $5 = (2+i)(2-i)$ in $\mathbb{Z}[i]$
  - $13 = (2+3i)(2-3i)$ in $\mathbb{Z}[i]$
  Both are primes of the form $4k+1$ in $\mathbb{Z}$ and factor in $\mathbb{Z}[i]$.